package william.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/3/4
 * @description <a href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode438_找到字符串中所有字母异位词 {
    /**
     * 采用滑动窗口法
     * 维护两个长度为26的int[26]词频表,记录每个字母出现的频率,两个数组相同位置的频率均相等,则两个字符串为字母异位词
     * 维护一个固定大小为p.length的窗口
     * 遍历数组,判断窗口中的字符串是否为p的字母异位词,逐次将窗口后移
     * <p>
     * 时间复杂度O(N) 只遍历数组一次
     * 空间复杂度O(1) 需要2个额外的int[26]的固定空间
     */
    public List<Integer> findAnagrams(String s, String p) {
        //边界条件校验
        if (s == null || s.isEmpty() || p == null || p.isEmpty()) {
            return Collections.emptyList();
        }

        int sLen = s.length();
        int pLen = p.length();
        if (sLen < pLen) {
            return Collections.emptyList();
        }

        //维护长度为p.length的固定窗口[l,r]
        int l = 0;
        int r = pLen - 1;

        //维护两个词频表,用于判断是否为字母异位词
        int[] sFrequency = new int[26];
        int[] pFrequency = new int[26];

        //初始化
        for (int i = l; i <= r; i++) {
            sFrequency[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < pLen; i++) {
            pFrequency[p.charAt(i) - 'a']++;
        }

        List<Integer> result = new ArrayList<>();

        //遍历数组,判断窗口中的字母是否为字母异位词,并将窗口依次右移
        while (true) {
            if (isAnagrams(sFrequency, pFrequency)) {
                //保存满足条件的索引
                result.add(l);
            }

            if (r >= sLen - 1) { //窗口到达最右,终止
                break;
            }

            //窗口右移,更新词频
            sFrequency[s.charAt(l++) - 'a']--;
            sFrequency[s.charAt(++r) - 'a']++;
        }


        //返回结果
        return result;

    }

    /**
     * 判断是否为字母异位词
     * 如果两个词频表相同位置的词频相等,则为字母异位词
     */
    private boolean isAnagrams(int[] sFrequency, int[] pFrequency) {
        for (int i = 0; i < 26; i++) {
            if (sFrequency[i] != pFrequency[i]) {
                return false;
            }
        }
        return true;
    }
}
